﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

     * 
     * 
     * */
    class Problem47 : IProblem
    {
        public string Calculate()
        {
            //taktika: (bruteforce)
            //za svaki broj, ako je prime, stavljat ga u listu primeova
            //ako nije prime, povecamo counterConsecutive za jedan
            //                radimo broj modulo prime za svaki od primeova u listi (do math.sqrt(broj)), i povecavamo counter
            //                (razlisli dali je točno n, ili >n ponavljanja!)
            //                ako je counter == n, break
            //                ako je kraj primeova, onda je counterConsecutive = 0;
            //ako je counterCounsecutive = n, rješenje je broj - n + 1;

            List<int> previousPrimes = new List<int>() {};

            int n = 4;
            int x = 1;

            int consecutiveCounter = 0;

            while (true)
            {
                x++;
                consecutiveCounter++;
                if (CommonFunctions.IsPrime(x))
                {
                    previousPrimes.Add(x);
                    consecutiveCounter = 0;
                }
                else
                {
                    int temp = x;
                    int counter = 0;
                    for (int i = 0; i < previousPrimes.Count; i++)
                    {
                        //if (Math.Sqrt(temp) < previousPrimes[i])
                        //    break; //nema smisla gledat primeove koji ga više nemogu podijelit.

                        if (temp == 1)
                            break;

                        if (temp % previousPrimes[i] == 0)
                        {
                            counter++;
                            while (temp % previousPrimes[i] == 0) // u slučaju više istih faktora
                            {
                                temp /= previousPrimes[i];
                            }
                        }
                    }

                    if (temp != 1 || counter != n) //ako se jos mogao dijelit ili ako nije bilo n faktora
                        consecutiveCounter = 0;
                }

                if (consecutiveCounter == n)
                    break;
            }


            for (int i = 0; i < n; i++)
            {
                Console.WriteLine(x - n + 1 + i);
            }
            return (x - n + 1).ToString();
        }
    }
}
